<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Longest Palindromic Substring</title>
        <style>
</style>
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.10.2/dist/katex.min.css" integrity="sha384-yFRtMMDnQtDRO8rLpMIKrtPCD5jdktao2TV19YiZYWMDkUR5GQZR/NOVTdquEx1j" crossorigin="anonymous">
<link href="https://cdn.jsdelivr.net/npm/katex-copytex@latest/dist/katex-copytex.min.css" rel="stylesheet" type="text/css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        <script src="https://cdn.jsdelivr.net/npm/katex-copytex@latest/dist/katex-copytex.min.js"></script>
        
    </head>
    <body class="vscode-light">
        <h1 id="longest-palindromic-substring">Longest Palindromic Substring</h1>
<h1 id="1-lc-5-longest-palindromic-substring">1. LC 5 Longest Palindromic Substring</h1>
<ul>
<li><a href="https://leetcode.com/problems/longest-palindromic-substring/">https://leetcode.com/problems/longest-palindromic-substring/</a></li>
<li><a href="https://www.youtube.com/watch?v=V-sEwsca1ak&amp;list=PLrmLmBdmIlpvxhscYQdvfFNWU_pdkG5de&amp;index=2">https://www.youtube.com/watch?v=V-sEwsca1ak&amp;list=PLrmLmBdmIlpvxhscYQdvfFNWU_pdkG5de&amp;index=2</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/string/LongestPalindromeSubstring.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/string/LongestPalindromeSubstring.java</a></li>
</ul>
<h2 id="1-manacher">1. manacher</h2>
<p>my version, O(nlng), 124 ms</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">longestPalindrome</span><span class="hljs-params">(self, s: str)</span> -&gt; str:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> s:
            <span class="hljs-keyword">return</span> <span class="hljs-string">""</span>
        
        s = <span class="hljs-string">"^#"</span> + <span class="hljs-string">"#"</span>.join(list(s)) + <span class="hljs-string">"#$"</span>
        right_most = <span class="hljs-number">0</span>
        center = <span class="hljs-number">0</span>
        n = len(s)
        dp = [<span class="hljs-number">0</span>] * n
    
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n<span class="hljs-number">-1</span>):  <span class="hljs-comment"># 这里不用遍历第一个字符^和最后一个字符$</span>
            j = center*<span class="hljs-number">2</span> - i
            <span class="hljs-keyword">if</span> i + dp[j] &lt; right_most:
                dp[i] = dp[j]
            <span class="hljs-keyword">else</span>:
                k = max(right_most - i,<span class="hljs-number">0</span>)
                <span class="hljs-keyword">while</span> s[i+k] == s[i-k]:
                    k += <span class="hljs-number">1</span>
                dp[i] = k - <span class="hljs-number">1</span>
                <span class="hljs-keyword">if</span> i + dp[i] &gt; right_most:
                    right_most = i + dp[i]
                    center = i
    
        max_i = <span class="hljs-number">0</span>
        max_v = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i, v <span class="hljs-keyword">in</span> enumerate(dp):
            <span class="hljs-keyword">if</span> v &gt; max_v:
                max_i = i
                max_v = v
        <span class="hljs-keyword">return</span> s[max_i-max_v:max_i+max_v+<span class="hljs-number">1</span>].replace(<span class="hljs-string">"#"</span>,<span class="hljs-string">""</span>)
</div></code></pre>
<p>还有一种写法，可以看这里， 就是细节处理不一样</p>
<ul>
<li><a href="https://leetcode.com/problems/longest-palindromic-substring/discuss/3337/Manacher-algorithm-in-Python-O(n)">https://leetcode.com/problems/longest-palindromic-substring/discuss/3337/Manacher-algorithm-in-Python-O(n)</a></li>
</ul>
<h2 id="12-从中心往两侧遍历">1.2 从中心往两侧遍历</h2>
<p>1208 ms</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">longestPalindrome</span><span class="hljs-params">(self, s: str)</span> -&gt; str:</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_helper</span><span class="hljs-params">(s, l, r)</span>:</span>
            k = <span class="hljs-number">0</span>
            <span class="hljs-keyword">while</span> l&gt;=<span class="hljs-number">0</span> <span class="hljs-keyword">and</span> r&lt;len(s) <span class="hljs-keyword">and</span> s[l] == s[r]:
                l -= <span class="hljs-number">1</span>
                r += <span class="hljs-number">1</span>
            <span class="hljs-keyword">return</span> s[l+<span class="hljs-number">1</span>:r]
    
        ans = <span class="hljs-string">""</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(s)):
            t1 = _helper(s, i, i)
            t2 = _helper(s, i, i+<span class="hljs-number">1</span>)
            ans = max(ans, t1, t2, key=len)
            
        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<h2 id="13-动态规划">1.3 动态规划</h2>
<p>6464 ms</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">longestPalindrome</span><span class="hljs-params">(self, s: str)</span> -&gt; str:</span>
        n = len(s)
        <span class="hljs-keyword">if</span> n &lt;= <span class="hljs-number">1</span>:
            <span class="hljs-keyword">return</span> s
        ans = <span class="hljs-number">1</span>
        ans2 = s[<span class="hljs-number">0</span>]
        
        dp = [[<span class="hljs-number">0</span>] * n <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(n)]
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            dp[i][i] = <span class="hljs-number">1</span>
            
            
            
        l = <span class="hljs-number">1</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n-l):
            j = i+l
            <span class="hljs-keyword">if</span> s[i] == s[j]:
                dp[i][j] = <span class="hljs-number">1</span>
                ans = <span class="hljs-number">2</span>
                ans2 = s[i:j+<span class="hljs-number">1</span>]
        
        <span class="hljs-keyword">for</span> l <span class="hljs-keyword">in</span> range(<span class="hljs-number">2</span>, n):
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n-l):
                j = i + l
                <span class="hljs-keyword">if</span> s[i] == s[j] <span class="hljs-keyword">and</span> dp[i+<span class="hljs-number">1</span>][j<span class="hljs-number">-1</span>] == <span class="hljs-number">1</span>:
                    dp[i][j] = <span class="hljs-number">1</span>
                    ans = max(ans, j - i + <span class="hljs-number">1</span>)
                    ans2 = s[i:j+<span class="hljs-number">1</span>]
        <span class="hljs-keyword">return</span> ans2
    
</div></code></pre>
<h1 id="2-lc-1312-minimum-insertion-steps-to-make-a-string-palindrome">2. LC 1312. Minimum Insertion Steps to Make a String Palindrome</h1>
<ul>
<li><a href="https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/">https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/</a></li>
</ul>
<p>Given a string s. In one step you can insert any character at any index of the string.</p>
<p>Return the minimum number of steps to make s palindrome.</p>
<p>A Palindrome String is one that reads the same backward as well as forward.</p>
<pre><code><code><div>Example 1:

Input: s = &quot;zzazz&quot;
Output: 0
Explanation: The string &quot;zzazz&quot; is already palindrome we don't need any insertions.
Example 2:

Input: s = &quot;mbadm&quot;
Output: 2
Explanation: String can be &quot;mbdadbm&quot; or &quot;mdbabdm&quot;.
Example 3:

Input: s = &quot;leetcode&quot;
Output: 5
Explanation: Inserting 5 characters the string becomes &quot;leetcodocteel&quot;.
Example 4:

Input: s = &quot;g&quot;
Output: 0
Example 5:

Input: s = &quot;no&quot;
Output: 1
</div></code></code></pre>
<p>本题和 <a href="kmp.html">kmp</a> 里面的 LC 214. Shortest Palindrome 不是一个类型，本题是dp, 而且是斜着遍历</p>
<p>参考labuladong 的文章  回文问题终极篇: 最小代价构造回文串</p>
<p>用dp[i][j] 表示改造字符串(i,j) 为回文串所需的最小字符， 最终所求就是dp[0][n-1]</p>
<p>下面是递推公式.</p>
<p>如果s[i] == s[j]</p>
<pre><code>例如 “X a b c X” 这样的字符串，那么 dp[i][j] = dp[i+1][j-1]
</code></pre>
<p>如果s[i] != s[j]</p>
<pre><code>这个时候，就比较微妙了。 和dp[i+1][j-1] 无关，而和dp[i+1][j], dp[i][j-1]有关系

例如 &quot;X a a a a&quot; 这样的字符串， 很明显是 dp[i][j] = dp[i+1][j] + 1

例如 &quot;a a a a X&quot; 这样的字符串， 很明显是 dp[i][j] = dp[i][j-1] + 1

例如 &quot;X a a b Y&quot; 这样的字符串， 就需要判断 dp[i+1][j] 和 dp[i][j-1] 哪个更小， dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
</code></pre>
<p>这个递推公式和那个 LC 516 最长回文子序列很相似</p>
<p>第一个版本</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">minInsertions</span><span class="hljs-params">(self, s: str)</span> -&gt; int:</span>
        n = len(s)
        dp = [[<span class="hljs-number">0</span>] * (n) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n)]
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            dp[i][i] = <span class="hljs-number">0</span>           <span class="hljs-comment"># 这个初始化没有必要</span>
            
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n<span class="hljs-number">-1</span>):
            j = i+<span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> s[i] == s[j]:
                dp[i][j] = <span class="hljs-number">0</span>
            <span class="hljs-keyword">else</span>:
                dp[i][j] = <span class="hljs-number">1</span>
            
        <span class="hljs-keyword">for</span> step <span class="hljs-keyword">in</span> range(<span class="hljs-number">2</span>, n):
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n-step):
                j = i + step
                <span class="hljs-keyword">if</span> s[i] == s[j]:
                    dp[i][j] = dp[i+<span class="hljs-number">1</span>][j<span class="hljs-number">-1</span>]
                <span class="hljs-keyword">else</span>:
                    dp[i][j] = min(dp[i+<span class="hljs-number">1</span>][j], dp[i][j<span class="hljs-number">-1</span>]) + <span class="hljs-number">1</span>
                    
        <span class="hljs-keyword">return</span> dp[<span class="hljs-number">0</span>][n<span class="hljs-number">-1</span>]
</div></code></pre>
<p>第二个版本</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">minInsertions</span><span class="hljs-params">(self, s: str)</span> -&gt; int:</span>
        n = len(s)
        dp = [[<span class="hljs-number">0</span>] * (n) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n)]
        <span class="hljs-comment">#for i in range(n):</span>
        <span class="hljs-comment">#    dp[i][i] = 0</span>
        <span class="hljs-comment">#    </span>
        <span class="hljs-comment">#for i in range(n-1):</span>
        <span class="hljs-comment">#    j = i+1</span>
        <span class="hljs-comment">#    if s[i] == s[j]:</span>
        <span class="hljs-comment">#        dp[i][j] = 0</span>
        <span class="hljs-comment">#    else:</span>
        <span class="hljs-comment">#        dp[i][j] = 1</span>
            
        <span class="hljs-keyword">for</span> step <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n):  <span class="hljs-comment"># 这里要从range(2, n)改成range(1, n)</span>
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n-step):
                j = i + step
                <span class="hljs-keyword">if</span> s[i] == s[j]:
                    dp[i][j] = dp[i+<span class="hljs-number">1</span>][j<span class="hljs-number">-1</span>]
                <span class="hljs-keyword">else</span>:
                    dp[i][j] = min(dp[i+<span class="hljs-number">1</span>][j], dp[i][j<span class="hljs-number">-1</span>]) + <span class="hljs-number">1</span>
                    
        <span class="hljs-keyword">return</span> dp[<span class="hljs-number">0</span>][n<span class="hljs-number">-1</span>]
</div></code></pre>

    </body>
    </html>